import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86185
 * Date: 2023-04-27
 * Time: 20:10
 */
public class Sort {
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int n = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if(array[j] > n) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = n;
        }
    }
    /**
     * 希尔排序
     * 不稳定
     * 时间复杂度O(n^1.3)
     * 空间复杂度O(1)
     * @param arr
     * @param gap
     */
    private static void shell(int[] arr, int gap) {
        for(int i = gap; i < arr.length; i++) {
            int n = arr[i];
            int j = i - gap;
            for(; j >= 0; j-=gap) {
                if(arr[j] > n) {
                    arr[j + gap] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + gap] = n;
        }
    }
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while(gap > 1) {
            gap /= 2;
            shell(arr, gap);
        }
    }

    /**
     * 选择排序
     * 时间复杂度为O(n^2)
     * 空间复杂度为O(1)
     * 不稳定
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[index] > arr[j]) {
                    index = j;
                }
            }
            swap(arr, i, index);
        }
    }
    private static void swap(int[] arr, int index1, int index2) {
        int n = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = n;
    }
    // 另一种
    public static void selectSort0(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (right > left) {
            int minIndex = left;
            int maxIndex = left;
            for(int i = left + 1; i <= right; i++) {
                if(arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(arr, minIndex, left);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(arr, maxIndex, right);

            left++;
            right--;
        }
    }


    /**
     * 堆排序
     * @param arr
     */
    public static void heapSort(int[] arr) {
        createBigHeat(arr);
        int end = arr.length - 1;
        while (end > 0) {
            swap(arr, 0, end);
            siftDown(arr, 0, end);
            end--;
        }
    }
    private static void createBigHeat(int[] arr) {
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr, i, arr.length);
        }
    }
    private static void siftDown(int[] arr, int parent, int len) {
        int child = parent * 2 + 1;
        while(child < len) {
            if(child + 1 < len && arr[child] < arr[child + 1]) {
                child++;
            }
            if(arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
    

    /**
     * 冒泡排序
     * 时间复杂度O(N^2)
     * 空间复杂度O(1)
     * 稳定
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        for(int i = 0; i <arr.length; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }

    /**
     * 快速排序
     * 时间复杂度为n*log(n)[好的情况] O(n^2)[数据是有序的]
     * 空间复杂度：O(logN)[好的情况] O(n)[数据是有序的]
     * 不稳定
     */
    public static void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }
    private static void insertSort2(int[] array, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int n = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if(array[j] > n) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = n;
        }
    }
    private static void quick(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }

        if(end - start + 1 <= 20) {
            //直接插入排序
            insertSort2(arr, start, end);
            return;
        }

        //三数取中法
        int midIndex = threeNum(arr, start, end);
        swap(arr, start, midIndex);

//        int pivot = partition(arr, start, end);
//        int pivot = partition2(arr, start, end);
        int pivot = partition3(arr, start, end);
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }
    private static int partition(int[] arr, int left, int right) {
        int index = left;
        int n = arr[left];
        while(left < right) {
            while(left < right && n <= arr[right]) {
                right--;
            }
            while(left < right && n >= arr[left]) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, index, left);
        return left;
    }
    private static int partition2(int[] arr, int left, int right) {
        int index = right;
        int n = arr[right];
        while(left < right) {
            while(left < right && n >= arr[left]) {
                left++;
            }
            while(left < right && n <= arr[right]) {
                right--;
            }
            swap(arr, left, right);
        }
        swap(arr, index, left);
        return left;
    }

    //挖坑法
    private static int partition3(int[] arr, int left, int right) {
        int n = arr[left];
        while(left < right) {
            while(left < right && n <= arr[right]) {
                right--;
            }
            arr[left] = arr[right];
            while(left < right && n >= arr[left]) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[right] = n;
//        System.out.println(Arrays.toString(arr));
        return left;
    }
    //优化
    /**
     * 三数取中法
     * @param arr
     * @param left
     * @param right
     * @return 中间数字的下标
     */
    private static int threeNum(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if(arr[left] < arr[right]) {
            if(arr[mid] < arr[left]) {
                return left;
            } else if (arr[mid] > arr[right]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (arr[mid] < arr[right]) {
                return right;
            } else if (arr[mid] > arr[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    /**
     * 非递归快速排序
     * 时间复杂度为O(logN)
     *
     * @param arr
     */
    public static void quickSort2(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = arr.length - 1;

        if(end - start + 1 <= 20) {
            //直接插入排序
            insertSort2(arr, start, end);
            return;
        }

        //三数取中法
        int midIndex = threeNum(arr, start, end);
        swap(arr, start, midIndex);

        int pivot = partition3(arr, start, end);
        if (pivot > start + 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if (pivot < end - 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }
        while (!stack.empty()) {
            end = stack.pop();
            start = stack.pop();
            if(end - start + 1 <= 20) {
                //直接插入排序
                insertSort2(arr, start, end);
            } else {
                //三数取中法
                midIndex = threeNum(arr, start, end);
                swap(arr, start, midIndex);
                pivot = partition3(arr, start, end);
                if (pivot > start + 1) {
                    stack.push(start);
                    stack.push(pivot - 1);
                }
                if (pivot < end - 1) {
                    stack.push(pivot + 1);
                    stack.push(end);
                }
            }
        }
    }

    /**
     * 归并排序(递归)
     * 时间复杂度O(n*logN)
     * 空间复杂度O(N)
     * 稳定的排序
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        int[] tmpArr = new int[right - left + 1];
        int k = 0;

        while(s1 <= e1 && s2 <= e2) {
            if(arr[s1] <= arr[s2]) {
                tmpArr[k++] = arr[s1++];
            } else {
                tmpArr[k++] = arr[s2++];
            }
        }
        while(s1 <= e1) {
            tmpArr[k++] = arr[s1++];
        }
        while (s2 <= e2) {
            tmpArr[k++] = arr[s2++];
        }

        for (int i = 0; i < k; i++) {
            arr[i + left] = tmpArr[i];
        }

    }
    private static void mergeFunc(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeFunc(arr, left, mid);
        mergeFunc(arr, mid + 1, right);

        merge(arr, left, mid, right);

    }
    public static void mergeSort(int[] arr) {
        mergeFunc(arr, 0, arr.length - 1);
    }

    /**
     * 非递归归并
     *
     */
    public static void mergeSort1(int[] arr) {
        int gap = 1;
        while(gap < arr.length) {
            for (int i = 0; i < arr.length; i+= gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if (mid >= arr.length) {
                    mid = arr.length - 1;
                }
                if(right >= arr.length) {
                    right = arr.length - 1;
                }
                merge(arr, left, mid, right);
            }
            gap *= 2;
        }
    }

    /**
     * 计数排序适用于给定范围，且范围较小
     * 时间复杂度O(n + 范围)
     * 空间复杂度O(范围)
     * @param arr
     */
    public static void countArray(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int len = max - min + 1;
        int[] count = new int[len];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }
        int k = 0;
        for (int i = 0; i < len; i++) {
            int n = count[i];
            while (n != 0) {
                arr[k++] = i + min;
                n--;
            }
         }
    }

    public static void radixSort (int[] arr){
        int maxDigit = getMaxDigit(arr);
        sort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private static int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLength(maxValue);
    }

    private static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected static int getNumLength(long num) {
        if (num == 0) {
            return 1;
        }
        int length = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            length++;
        }
        return length;
    }
    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
    private static int[] sort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {

            int[][] counter = new int[20][0];
            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + 10;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;//重新赋值
                    System.out.print(value + " ");
                }
            }
            System.out.println("\n");
        }

        return arr;
    }

    public static void countSort(int[] arr) {
        int len = arr.length;
        int max = arr[0];
        for(int i = 1; i < len; i++) {
            if(arr[i] > max) {
                max = arr[i];
            }
        }
        int[] count = new int[max + 1];
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            count[arr[i]]++;
        }
        for (int i = 1; i < max + 1; i++) {
            count[i] += count[i-1];
        }
        for (int i = len - 1; i >= 0; i--) {
            int n = count[arr[i]];
            ans[n - 1] = arr[i];
            count[arr[i]]--;
        }
        for (int i = 0; i < len; i++) {
            arr[i] = ans[i];
        }
    }

    public static void bucketSort(int[] arr){

        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<>());
        }

        // 将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        // 对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for(int i = 0; i < bucketArr.size(); i++){
            for(int j = 0; j < bucketArr.get(i).size(); j++){
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
    }


    public static void main(String[] args) {
        int[] arr = {3,44,38,5,47,15,36,-55,-62,-10,-3,-7,-5,-26,-73,-66,26,27,2,46,4,19,50,48,189,176,542,946,235,158,264,496,576,127,555,864,1788,1469};
        int[] arr2 = {2,5,3,0,2,3,0,3};
        //shellSort(arr);
//        selectSort(arr);
//        heapSort(arr);
//        bubbleSort(arr);
//        quickSort(arr);
//        insertSort(arr);
//        quickSort2(arr);
//        mergeSort(arr);
//        countArray(arr);
        radixSort(arr);
//        countSort(arr2);
        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(ans));
    }

}
